#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>
#include "HeapSort.h"

std::vector<int> generateRandomSequence(size_t size) {
    std::vector<int> vec(size);
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(1, 1000000);

    for (auto& item : vec) {
        item = dis(gen);
    }
    return vec;
}

std::vector<int> generateOrderedSequence(size_t size) {
    std::vector<int> vec(size);
    for (size_t i = 0; i < size; ++i) {
        vec[i] = i;
    }
    return vec;
}

std::vector<int> generateReversedSequence(size_t size) {
    std::vector<int> vec(size);
    for (size_t i = 0; i < size; ++i) {
        vec[i] = size - i - 1;
    }
    return vec;
}

std::vector<int> generateRepetitiveSequence(size_t size) {
    std::vector<int> vec(size);
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(1, 100);

    for (auto& item : vec) {
        item = dis(gen);
    }
    return vec;
}

int main() {
    size_t size = 1000000;

    auto randomVec = generateRandomSequence(size);
    auto randomVecCopy = randomVec;

    auto start = std::chrono::high_resolution_clock::now();
    heapSort(randomVec, lessThan);
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> elapsed = end - start;
    std::cout << "Heap Sort Random: " << elapsed.count() << " ms, Correct: " << checkSorted(randomVec, lessThan) << std::endl;

    start = std::chrono::high_resolution_clock::now();
    std::sort_heap(randomVecCopy.begin(), randomVecCopy.end());
    end = std::chrono::high_resolution_clock::now();
    elapsed = end - start;
    std::cout << "std::sort_heap() Random: " << elapsed.count() << " ms " << std::endl;

    auto sortedVec = generateOrderedSequence(size);
    auto sortedVecCopy = sortedVec;

    start = std::chrono::high_resolution_clock::now();
    heapSort(sortedVec, lessThan);
    end = std::chrono::high_resolution_clock::now();
    elapsed = end - start;
    std::cout << "Heap Sort Ordered: " << elapsed.count() << " ms, Correct: " << checkSorted(sortedVec, lessThan) << std::endl;

    start = std::chrono::high_resolution_clock::now();
    std::sort_heap(sortedVecCopy.begin(), sortedVecCopy.end());
    end = std::chrono::high_resolution_clock::now();
    elapsed = end - start;
    std::cout << "std::sort_heap() Ordered: " << elapsed.count() << " ms "  << std::endl;

    auto reversedVec = generateReversedSequence(size);
    auto reversedVecCopy = reversedVec;

    start = std::chrono::high_resolution_clock::now();
    heapSort(reversedVec, lessThan);
    end = std::chrono::high_resolution_clock::now();
    elapsed = end - start;
    std::cout << "Heap Sort Reversed: " << elapsed.count() << " ms, Correct: " << checkSorted(reversedVec, lessThan) << std::endl;

    start = std::chrono::high_resolution_clock::now();
    std::sort_heap(reversedVecCopy.begin(), reversedVecCopy.end());
    end = std::chrono::high_resolution_clock::now();
    elapsed = end - start;
    std::cout << "std::sort_heap() Reversed: " << elapsed.count() << " ms "  << std::endl;

    auto partiallyRepeatedVec = generateRepetitiveSequence(size);
    auto partiallyRepeatedVecCopy = partiallyRepeatedVec;

    start = std::chrono::high_resolution_clock::now();
    heapSort(partiallyRepeatedVec, lessThan);
    end = std::chrono::high_resolution_clock::now();
    elapsed = end - start;
    std::cout << "Heap Sort Repetitive: " << elapsed.count() << " ms, Correct: " << checkSorted(partiallyRepeatedVec, lessThan) << std::endl;

    start = std::chrono::high_resolution_clock::now();
    std::sort_heap(partiallyRepeatedVecCopy.begin(), partiallyRepeatedVecCopy.end());
    end = std::chrono::high_resolution_clock::now();
    elapsed = end - start;
    std::cout << "std::sort_heap() Repetitive: " << elapsed.count() << " ms "  << std::endl;

    return 0;
}